﻿//typedef int QDateType;
//typedef struct QueueNode
//{
//	struct QueueNode* next;
//	QDateType date;
//}QNode;
//
//typedef struct Queue//不传二级指针有三种方式：带哨兵位、有返回值、结构体封装
//{
//	QNode* head;
//	QNode* tail;
//	int size;
//}Que;
//
//void QueueInit(Que* pq);
//void QueueDestory(Que* pq);
//void QueuePush(Que* pq, QDateType x);
//void QueuePop(Que* pq);
//QDateType QueueFront(Que* pq);
//QDateType QueueBack(Que* pq);
//bool QueueEmpty(Que* pq);
//int QueueSize(Que* pq);
//
//void QueueInit(Que* pq)
//{
//	assert(pq);
//
//	pq->head = pq->tail = NULL;
//	pq->size = 0;
//}
//
//
//void QueueDestory(Que* pq)
//{
//	assert(pq);
//
//	QNode* cur = pq->head;
//	while (cur)
//	{
//		QNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	pq->tail = pq->head = NULL;
//	pq->size = 0;
//}
//
//void QueuePush(Que* pq, QDateType x)
//{
//	assert(pq);
//
//	QNode* newnode = (QNode*)malloc(sizeof(QNode));
//	if (newnode == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//	newnode->date = x;
//	newnode->next = NULL;
//
//	if (pq->tail == NULL)
//		pq->head = pq->tail = newnode;
//	else
//	{
//		pq->tail->next = newnode;
//		pq->tail = newnode;
//	}
//
//	pq->size++;
//}
//
//void QueuePop(Que* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//
//	if (pq->head->next == NULL)
//	{
//		free(pq->head);
//		pq->head = pq->tail = NULL;
//	}
//	else
//	{
//		QNode* next = pq->head->next;
//		free(pq->head);
//		pq->head = next;
//	}
//
//	pq->size--;
//}
//
//QDateType QueueFront(Que* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//
//	return pq->head->date;
//}
//
//QDateType QueueBack(Que* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//
//	return pq->tail->date;
//}
//
//bool QueueEmpty(Que* pq)
//{
//	assert(pq);
//
//	return pq->head == NULL;
//}
//
//int QueueSize(Que* pq)
//{
//	assert(pq);
//
//	return pq->size;
//}
//
//
//typedef struct {
//	Que q1;
//	Que q2;
//} MyStack;
//
//
//MyStack* myStackCreate() {
//	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
//	if (pst == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//	QueueInit(&pst->q1);
//	QueueInit(&pst->q2);
//
//	return pst;
//}
//
//void myStackPush(MyStack* obj, int x) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		QueuePush(&obj->q1, x);
//	}
//	else
//	{
//		QueuePush(&obj->q2, x);
//	}
//}
//
//int myStackPop(MyStack* obj) {
//	Que* empty = &obj->q1;
//	Que* nonempty = &obj->q2;
//	if (!QueueEmpty(&obj->q1))
//	{
//		empty = &obj->q2;
//		nonempty = &obj->q1;
//	}
//
//	//将前size-1个导入非空
//	while (QueueSize(nonempty) > 1)
//	{
//		QueuePush(empty, QueueFront(nonempty));
//		QueuePop(nonempty);
//	}
//
//	int top = QueueFront(nonempty);//模拟栈的顶
//	QueuePop(nonempty);
//	return top;
//}
//
//int myStackTop(MyStack* obj) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		return QueueBack(&obj->q1);
//	}
//	else
//	{
//		return QueueBack(&obj->q2);
//
//	}
//}
//
//bool myStackEmpty(MyStack* obj) {
//	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
//}
//
//void myStackFree(MyStack* obj) {
//	QueueDestory(&obj->q1);
//	QueueDestory(&obj->q2);
//	free(obj);
//}





typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;//ջ
	int capacity;//
}ST;


void STInit(ST* ps);
void STDestory(ST* ps);
void STPush(ST* ps, STDateType x);
void STPop(ST* ps);

STDateType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}


void STDestory(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void STPush(ST* ps, STDateType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(ps->a, newCapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

STDateType STTop(ST* ps)
{
	assert(ps);

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	return ps->top == 0;
}

typedef struct {
	ST pushst;
	ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (obj == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	STInit(&obj->pushst);
	STInit(&obj->popst);
	return obj;
}

void myQueuePush(MyQueue* obj, int x) {
	STPush(&obj->pushst, x);
}

int myQueuePeek(MyQueue* obj) {
	if (STEmpty(&obj->popst))
	{
		//导数据
		while (!STEmpty(&obj->pushst))
		{
			STPush(&obj->popst, STTop(&obj->pushst));
			STPop(&obj->pushst);
		}
	}
	return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj) {
	int front = myQueuePeek(obj);
	STPop(&obj->popst);
	return front;
}

bool myQueueEmpty(MyQueue* obj) {
	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
	STDestory(&obj->pushst);
	STDestory(&obj->popst);
	free(obj);
}